//排序 
let array = [3,2,23,33,32,31,51,62,33,37,21,10,0]


array.sort((a,b) => a-b)

function mp(arr) {
  let length = arr.length
  for(let i = 0;i<length-1;i++) {
    for(let j = 0;j<length-1-i;j++) {
      if(arr[j]>arr[j+1]) {
        let tem = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = tem
      }
    }
  }
}
// mp(array)
// console.log(array)

//选择排序
function selectSort(arr) {
  let length = arr.length
  for (let i = 0; i < length-1; i++) {
    let min = i
    for (let j = i+1; j < length; j++) {
      if(arr[j]<arr[min]) {
        min = j
      }
    }
    //min就是我找到的最小的值的索引
    let tem = arr[i]
    arr[i] = arr[min]
    arr[min] = tem
  }
}
// selectSort(array)
// console.log(array)
//快排 [3,2,23,33,32,31,51,62,33,37,21,10,0] leftArr:[2,0] 3 rightArr:[...]

// leftArr:[2,0]   leftArr:[0] 2 right:[]


//3

//rightArr:[23,33,32,31]  leftArr:[]  23 rightArr:[33,32,31]

// function quickSort(arr) {
//   let length = arr.length
//   if(length<=1) return arr
//   const baseNum = arr[0]
//   const leftArr = []
//   const rightArr = []
//   for(let i = 1;i<length;i++) {
//     if(arr[i]<baseNum) {leftArr.push(arr[i])}
//     else {rightArr.push(arr[i])}
//   }
//   return [...quickSort(leftArr),baseNum,...quickSort(rightArr)]
// }
// const result = quickSort(array)

// console.log(result)
let arr3 = [20, 25, 28, 22, 30, 27]
function kp(arr) {
  let length = arr.length
  if(length<=1) return arr
  const baseNum = arr[0]
  const leftArr = []
  const rightArr = []
  for (let i = 1; i < arr.length; i++) {
    if(arr[i]<baseNum) {
      leftArr.push(arr[i])
    } else {
      rightArr.push(arr[i])
    }
  }
  return[...kp(leftArr), baseNum, ...kp(rightArr)]
}
console.log(kp(arr3))


















//冒泡
// function bubbleSort(arr) {
//   let length = arr.length;
//   for (let i = 0; i < length - 1; i++) {
//     for (let j = 0; j < length - 1 - i; j++) {
//       if (arr[j] > arr[j + 1]) {
//         const temp = arr[j];
//         arr[j] = arr[j + 1];
//         arr[j + 1] = temp;
//       }
//     }
//   }
// }
// let arr = [4, 8, 0, 1, 43, 53, 22, 11, 0];
// bubbleSort(arr)
// console.log(arr)
// //选择排序
// function selectSort(arr) {
//   let length = arr.length;
//   for(let i =0;i<length-1;i++) {
//     let minIndex = i
//     for(let j = i+1;j<length;j++) {
//       if(arr[j]<arr[minIndex]) {
//         minIndex = j
//       }
//     }
//     const temp = arr[i]
//     arr[i] = arr[minIndex]
//     arr[minIndex] = temp
//   }
// }
// let arrForSelect = [4, 8, 0, 1, 43, 53, 22, 11, 0];
// selectSort(arrForSelect)
// console.log(arrForSelect)
// //插入排序
// function insertSort(arr) {
//   let length = arr.length
//   for (let index = 1; index <length; index++) {
//     const temp = arr[index] //8 0 1
//     let j = index //1 2 3
//     while(j>0) {
//       if(arr[j-1]>temp) {
//         arr[j] = arr[j-1]
//       } else {
//         break
//       }
//       j--
//     }
//     arr[j] = temp
//   }
// }
// let arrInsert = [4, 8, 0, 1, 43, 53, 22, 11, 0];
// insertSort(arrInsert)
// console.log(arrInsert)
// //合并排序
// function mergeSort(arr) {
//   if(arr.length===1) return arr
//   const midIndex = Math.floor(arr.length/2)
//   const leftArr = arr.slice(0, midIndex) //[4,8,0,1],[4,8],[4]
//   const rightArr = arr.slice(midIndex, arr.length)//[43,53,22,11,0],[0,1],[8]
//   const leftResultArr = mergeSort(leftArr) //[4,8,0,1]
//   const rightResultArr = mergeSort(rightArr) //[43,53,22,11,0]
//   const tempArr = []
//   while(leftResultArr.length || rightResultArr.length) {
//     console.log('-------',leftResultArr, rightResultArr)
//     if(leftResultArr.length>0 && rightResultArr.length>0) {
//       tempArr.push(leftResultArr[0]<rightResultArr[0]?leftResultArr.shift():rightResultArr.shift())
//     } else if(leftResultArr.length>0) {
//       tempArr.push(leftResultArr.shift())
//     } else if(rightResultArr.length>0) {
//       tempArr.push(rightResultArr.shift())
//     }
//   }
//   console.log(tempArr)
//   return tempArr
// }
// let arrMerge = [4, 8, 0, 1, 43, 53, 22, 11, 0];
// let result = mergeSort(arrMerge)
// console.log(result)
// //快速排序
// function quickSort(arr) {
//   let length = arr.length
//   console.log(length)
//   if(length<=1) return arr
//   const baseNum = arr[0]
//   console.log(baseNum)
//   const leftArr = []
//   const rightArr = []
//   for(let i = 1;i<length;i++) {
//     if(arr[i]<baseNum) {leftArr.push(arr[i])}
//     else {rightArr.push(arr[i])}
//   }

    // return [...quickSort(leftArr),baseNum,...quickSort(rightArr)]
// }

